题目

题目描述

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入输出格式

输入格式：

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式：

一个整数，即牧场分配总方案数除以100,000,000的余数。

输入样例

1
2
3

2 3
1 1 1
0 1 0

输出样例

题解

一道状态压缩入门题，也是第一道我在不看任何题解的情况下写出来的状压dp题
状压dp一般会有明显的数据范围特征，即n,m一般都在20以内

状压dp的状态设计和转移是有套路的，就拿这道题来说，$f[i][j]$表示第$i$行在状态$j$的时候的方案数，其中$j$我们用一个二进制数来表示。
转移的时候只要判断与当前行和上一行是否冲突即可，如果不冲突，$f[i][j]=\sum_{z为不冲突的状态} f[i-1][z]$

$\sum_{1\le i\le cnt} f[n][i]$ 就是最后的答案（$cnt$为状态总数）

至于为什么在下面的代码里先枚举本层，在枚举上一层：
因为我们动态规划是靠状态转移来实现的，上一行相当于处在i-1阶段，我们需要不断用上一个阶段来更新下一个阶段（逆推），因此本层循环在外侧。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=100000000;
int f[13][5000];
int ok[13];//纪录每一行输入的数据，也是用二进制保存
int n,m;
int can[5000],cnt;//预处理出所有合法状态

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            cin>>a;
            ok[i]<<=1;//这里的顺序一定要注意
            ok[i]|=a;
        }
    }
    int MAXN=(1<<m)-1;//假设m为5最大的状态显然为1 1 1 1 1
    for(int i=0;i<=MAXN;i++)if((i&(i<<1))==0)can[++cnt]=i;//自己如果和自己左移重叠了，说明有相邻的，不合法，只有不重叠才合法，注意从0开始
    for(int i=1;i<=cnt;i++){
        if(can[i]&(~ok[1]))continue;//第一行单独处理，~按位取反
        f[1][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=cnt;j++){//枚举当前行
            int x=can[j];
            for(int z=1;z<=cnt;z++){//枚举上一行
                int y=can[z];
                if(x&y||x&(~ok[i])||y&(~ok[i-1]))continue;
                f[i][j]=(f[i][j]+f[i-1][z])%mod;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++)ans=(ans+f[n][i])%mod;
    cout<<ans;
    return 0;
}